package com.peng.leetcode.graph;

import java.util.*;

/**
 * EventualSafeNodes
 *
 * @author: lupeng6
 * @create: 2021/1/13 20:54
 */
public class EventualSafeNodes {

    public static void main(String[] args) {
        int[][] graph = new int[][]{{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}};
        List<Integer> integers = new EventualSafeNodes().eventualSafeNodes(graph);
        System.out.println(integers);
    }

    /**
     * 拓扑排序,
     * 顶点 vertex
     * 边 edge
     * 入度 inDegree
     * 出度 outDegree
     * 邻居 adjacency
     *
     * @author lupeng6
     * @date 2021/1/13 21:04
     */
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> result = new ArrayList<>();

        List<Set<Integer>> graphs = new ArrayList<>();
        List<Set<Integer>> reverseGraphs = new ArrayList<>();

        for (int i = 0; i < graph.length; i++) {
            graphs.add(new HashSet<>());
            reverseGraphs.add(new HashSet<>());
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < graph.length; i++) {
            int[] ints = graph[i];
            if (ints.length == 0) {
                queue.offer(i);
            } else {
                for (int j : ints) {
                    graphs.get(i).add(j);
                    reverseGraphs.get(j).add(i);
                }
            }
        }

        while (!queue.isEmpty()) {
            Integer poll = queue.poll();
            result.add(poll);
            Set<Integer> set = reverseGraphs.get(poll);
            for (Integer integer : set) {
                Set<Integer> in = graphs.get(integer);
                in.remove(poll);
                if (in.isEmpty()) {
                    queue.offer(integer);
                }
            }
        }

        Collections.sort(result);

        return result;
    }
}
